package leetcodev1.数组;

import java.util.*;

//对撞指针 从两头同时开始遍历
public class Solution2 {

    //非递减顺序排列
    //循环遍历两遍
    //超时
    public int[] twoSum(int[] numbers, int target) {
        int[] ret = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    ret[0] = i + 1;
                    ret[1] = j + 1;
                    return ret;
                }
            }
        }
        return ret;
    }

    //空间换时间
    public int[] twoSum1(int[] numbers, int target) {
        int[] ret = new int[2];
        Map<Integer, Integer> dict = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            dict.put(numbers[i], i);
        }

        for (int i = 0; i < numbers.length; i++) {
            int other = target - numbers[i];
            if (dict.containsKey(other)) {
                ret[0] = i + 1;
                ret[1] = dict.get(other) + 1;
                return ret;
            }
        }
        return ret;
    }

    //双指针 指针对撞法
    //最左+最右是一个临界值，可以增加，可以减少
    public int[] twoSum2(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left <= right) {
            if (numbers[left] + numbers[right] < target) {
                left++;
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                return new int[]{left + 1, right + 1};
            }
        }
        return new int[]{-1, -1};
    }

    //一边遍历，一边二分
    public int[] twoSum3(int[] numbers, int target) {
        return new int[]{-1, -1};
    }


    //正序和逆序一样
    //双指针遍历
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            char x = s.charAt(i);
            char y = s.charAt(j);
            if (!('0' <= x && x <= '9') && !('a' <= x && x <= 'z') && !('A' <= x && x <= 'Z')) {
                ++i;
                continue;
            }
            if (!('0' <= y && y <= '9') && !('a' <= y && y <= 'z') && !('A' <= y && y <= 'Z')) {
                --j;
                continue;
            }
            if ((x & 0xDF) != (y & 0xDF)) { // 全部转换成大写
                return false;
            }
            ++i;
            --j;
        }
        return true;
    }

    public String reverseVowels(String s) {
        int left = 0, right = s.length() - 1;
        char[] ret = new char[s.length()];
        while (left <= right) {
            if (!vowel(s.charAt(left))) {
                ret[left] = s.charAt(left);
                left++;
                continue;
            } else if (!vowel(s.charAt(right))) {
                ret[right] = s.charAt(right);
                right--;
                continue;
            }
            ret[left] = s.charAt(right);
            ret[right] = s.charAt(left);
            left++;
            right--;
        }
        return new String(ret);
    }

    private boolean vowel(char vow) {
        return vow == 'a' || vow == 'e' || vow == 'i' || vow == 'o' || vow == 'u' || vow == 'A' || vow == 'E' || vow == 'I' || vow == 'O' || vow == 'U';
    }

    //双重循环遍历 肯定可以得到结果
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, ret = 0, area;
        while (left < right) {
            area = getArea(right - left, Math.min(height[left], height[right]));
            ret = Math.max(ret, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ret;
    }

    private int getArea(int width, int height) {
        return width * height;
    }
}
